package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.*;

/**
 * 哈希<br>
 * 数组、哈希表、字符串、排序<br>
 * 中等
 *
 * <h1>49. 字母异位词分组</h1>
 *
 * <p>给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。</p>
 *
 * <p>字母异位词 是由重新排列源单词的所有字母得到的一个新单词。</p>
 */
public class A02GroupAnagrams {
    public static void main(String[] args) {
        A02GroupAnagrams groupAnagrams = new A02GroupAnagrams();

        String[] strs = new String[]{"eat","tea","tan","ate","nat","bat"};

        System.out.println("基础数据");
        TimeCostUtil.timeCost("排序_自己写的", () -> groupAnagrams.solution1_mine(strs));
        TimeCostUtil.timeCost("排序", () -> groupAnagrams.solution1(strs));
        TimeCostUtil.timeCost("计数", () -> groupAnagrams.solution2(strs));

        String[] strs2 = new String[1000000]; // 100万
        Random r = new Random();
        for (int i = 0; i < strs2.length; i++) {
            StringBuffer sb = new StringBuffer();
            for (int j = 0; j < 4; j++) {
                sb.append((char) ('a' + r.nextInt(26)));
            }
            strs2[i] = sb.toString();
        }
        System.out.println("大数据量");
        TimeCostUtil.timeCost("排序_自己写的", () -> groupAnagrams.solution1_mine(strs2));
        TimeCostUtil.timeCost("排序", () -> groupAnagrams.solution1(strs2));
        TimeCostUtil.timeCost("计数", () -> groupAnagrams.solution2(strs2));
    }

    // 排序自己写的
    public List<List<String>> solution1_mine(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);
            /*if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }
            map.get(sortedStr).add(str);*/
            map.computeIfAbsent(sortedStr, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    // 排序
    public List<List<String>> solution1(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }

    // 计数
    public List<List<String>> solution2(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }
}
